//------------------------------------------------------------------
//	linked List functions
//------------------------------------------------------------------

#ifndef LIST_H
#define LIST_H

//------------------------------------------------------------------
//	simple doubly-linked List
//------------------------------------------------------------------
class TList
{
public:
	template <class X>
	static inline void Init( X *pNode )
	{
		pNode->m_pNext = pNode->m_pPrev = pNode;
	}

	template <class X>
	static inline X *GetNext( X *a )
	{
		return a->m_pNext;
	}

	template <class X>
	static inline X *GetPrev( X *a )
	{
		return a->m_pPrev;
	}

	template <class X>
	static inline void Remove( X *a )
	{
		a->m_pPrev->m_pNext = a->m_pNext;
		a->m_pNext->m_pPrev = a->m_pPrev;
		a->m_pNext = a->m_pPrev = a;
	}

	template <class X>
	static inline void InsertAfter( X *a, X *newParent )
	{
		a->m_pNext = newParent->m_pNext;
		a->m_pPrev = newParent;
		newParent->m_pNext = a->m_pNext->m_pPrev = a;
	}

	template <class X>
	static inline void InsertBefore( X *a, X *newParent )
	{
		a->m_pNext = newParent;
		a->m_pPrev = newParent->m_pPrev;
		newParent->m_pPrev = a->m_pPrev->m_pNext = a;
	}

	template <class X>
	static inline void Reparent( X *a, X *newParent )
	{
		a->m_pPrev->m_pNext = a->m_pNext;
		a->m_pNext->m_pPrev = a->m_pPrev;
		InsertAfter(a,newParent);
	}

	template <class X>
	static inline bool IsEmpty( X *a )
	{
		return (a->m_pNext==a) && (a->m_pPrev==a);
	}

	// simple insertion sort
	// X needs to implement operator < with const X *
	template <class X>
	static inline void Sort( X *head )
	{
		X	*Item,*nextItem,*afterItem;

		nextItem = head->m_pNext->m_pNext;
		while( (Item=nextItem)!=head )
		{
			nextItem = Item->m_pNext;
			if( Item[0]<Item->.m_pPrev )
			{
				afterItem = Item->m_pPrev->m_pPrev;
				Remove(Item);
				while( afterItem!=head && Item[0]<afterItem )
					afterItem = afterItem->m_pPrev;
				InsertAfter(Item,afterItem);
			}
		}
	}

};

//------------------------------------------------------------------
//	single direction, doubly-linked List
//------------------------------------------------------------------
class TUniList
{
public:
	template <class X>
	static inline void Init( X *node )
	{
		node->m_pNext = 0;
		node->m_ppMe = 0;
	}

	template <class X>
	static inline X *GetNext( X *a )
	{
		return a->m_pNext;
	}

	template <class X>
	static inline X **GetNextPtr( X *a )
	{
		return &a->m_pNext;
	}

	template <class X>
	static inline void Remove( X *a )
	{
		if( a->m_ppMe )
		{
			*a->m_ppMe = a->m_pNext;
			if( a->m_pNext )	a->m_pNext->m_ppMe = a->m_ppMe;
			Init(a);
		}
	}

	template <class X>
	static inline void Insert( X *a, X **m_ppMe )
	{
		a->m_ppMe = m_ppMe;
		a->m_pNext = *m_ppMe;
		*m_ppMe = a;
		if( a->m_pNext )	a->m_pNext->m_ppMe = &a->m_pNext;
	}

	template <class X>
	static inline void Reparent( X *a, X **ppMe )
	{
		if( a->m_ppMe )
		{	// remove from current List
			*a->m_ppMe = a->m_pNext;
			if( a->m_pNext )	a->m_pNext->m_ppMe = a->m_ppMe;
		}

		Insert(a, ppMe );
	}

	template <class X>
	static inline void MoveList( X **ppNewBase, X *pMoveMe  )
	{
		// zero out the pointer to the moving List
		if( pMoveMe->m_ppMe )
			*pMoveMe->m_ppMe = 0;

		// add the join section to the end of the input strip
		pMoveMe->m_ppMe = ppNewBase;
		*ppNewBase = pMoveMe;
	}

	template <class X>
	static inline void JoinLists( X *pList, X *pJoin )
	{
		// find the end of the strip I want to join to
		while( pList->m_pNext )
			pList = pList->m_pNext;

		MoveList( &pList->m_pNext, pJoin );
	}


	template <class X>
	static inline void Setup( X *pFirst, u32 num, X **ppMe )
	{
		while( num-- )
		{
			Insert( pFirst, ppMe );
			pFirst++;
		}
	}
};

//------------------------------------------------------------------
//	object-independent doubly-linked List
//------------------------------------------------------------------
//	Each object in the List is represented by an IListItem
//------------------------------------------------------------------
//	When an object is deleted, it is not removed from the List
//	whilst there are any references on the IListItem. This .m_pPrevents
//	the IListItem from being removed from the List whilst it is
//	referenced in an iterator
//------------------------------------------------------------------
class TIListItem;
class CIList;
template<class X>class TIListIterator;

//-----------------------------------------------------------------------
//	an Item in the object-independent doubly-linked List
//-----------------------------------------------------------------------
class TIListItem
{
	friend class CIList;
public:
	TIListItem	*m_pNext;
	TIListItem	*m_pPrev;
	u32			m_nRefCount: 31;		//	reference count to prevent premature deletion
	u32			m_bDeleted :  1;		//	has this Item been deleted, but not removed?
	void		*m_pData;

public:
	TIListItem() : m_pData(0), m_bDeleted(0), m_nRefCount(1)
	{
		TList::Init(this);
	}

	inline u32	AddRef()
	{
		return ++m_nRefCount;
	}
	inline void ReleaseRef()
	{
		if( (--m_nRefCount)==0 )
			ReleaseItem(this);
	}

protected:
	static inline TIListItem	*GetItem()
	{
		TIListItem	*ret;
		while( (ret=TList::GetNext(&s_freeItems))==&s_freeItems )
			AllocItems();
		TList::Remove(ret);
		ret->m_nRefCount	= 1;
		ret->m_bDeleted		= 0;
		ret->m_pData		= 0;
		return ret;
	}

	static void	ReleaseItem( TIListItem *pItem )
	{
		TList::Reparent( pItem, &s_freeItems );
	}

	static void	AddClient()
	{
		++s_numClients;
	}
	static void	RemoveClient()
	{
		if( (--s_numClients)==0 )
			FreeItems();
	}

	static void		AllocItems();
	static void		FreeItems();
protected:

	static	u32			s_numClients;
	static	TIListItem	s_allocedItems;
	static	TIListItem	s_freeItems;
};

//-----------------------------------------------------------------------
//	List class
//-----------------------------------------------------------------------
class CIList
{
	friend class TList;
	friend class TIListIterator< class X >;

public:
	CIList()
	{
		TIListItem::AddClient();
	}
	~CIList()
	{
		while( m_Head.m_pNext!=&m_Head )
			TIListItem::ReleaseItem(m_Head.m_pNext);

		TIListItem::RemoveClient();
	}

	//---------------------------------------------------------------
	// is the List empty?
	//---------------------------------------------------------------
	inline	bool IsEmpty( )
	{
		return TList::IsEmpty(&m_Head);
	}

	//---------------------------------------------------------------
	// is an Item in the List?
	//---------------------------------------------------------------
	inline	bool IsInList( void *ptr )
	{
		return FindItem(ptr)!=0;
	}

	//---------------------------------------------------------------
	// add an Item to the List
	//---------------------------------------------------------------
	inline	bool AddItem( void *ptr )
	{
		TIListItem	*pNewItem;

		if( FindItem(ptr)!=0 )
			return false;

		pNewItem = TIListItem::GetItem();
		TList::InsertBefore(pNewItem,&m_Head);
		pNewItem->m_pData = ptr;
		return true;
	}

	//---------------------------------------------------------------
	// remove an Item from the List
	//---------------------------------------------------------------
	inline	bool RemoveItem( void *ptr )
	{
		TIListItem	*pItem;
		if( (pItem = FindItem(ptr)) == 0 )
			return false;

		// delete this Item
		pItem->m_bDeleted = 1;
		pItem->ReleaseRef();
		return true;
	}

	//---------------------------------------------------------------
	//	get the m_Head of the List.
	//	The m_Head must be released using Item->ReleaseRef() when done
	//---------------------------------------------------------------
	inline	TIListItem	*GetHead()
	{
		m_Head.AddRef();
		return &m_Head;
	}

	//---------------------------------------------------------------
	//	get the next Item in the List.
	//	This releases the .m_pPrevious Item and releases any
	//	non-referenced deleted Items it comes across.
	//	The returned Item must be released using Item->ReleaseRef()
	//---------------------------------------------------------------
	TIListItem	*GetNext( TIListItem *pCurrent )
	{
		TIListItem	*pPrevItem;
		while( (pPrevItem=pCurrent)!=0 )
		{
			pCurrent = TList::GetNext(pCurrent);

			// if .m_pPrev Item has no refs and is deleted, release it
			pPrevItem->ReleaseRef();

			// are we back at the m_Head of the List?
			if( pCurrent==&m_Head )
				return 0;

			// increase the reference count
			pCurrent->AddRef();
			if( !pCurrent->m_bDeleted )
				return pCurrent;
		}
		return 0;
	}

protected:
	//---------------------------------------------------------------
	//	find an Item in the List
	//---------------------------------------------------------------
	TIListItem	*FindItem( void *ptr )
	{
		TIListItem	*ret;
		for( ret=TList::GetNext(&m_Head); ret!=&m_Head; ret=TList::GetNext(ret) )
		{
			if( ret->m_bDeleted )
				continue;
			if( ret->m_pData == ptr )
				return ret;
		}
		return 0;
	}

protected:
	TIListItem	m_Head;
};

//-----------------------------------------------------------------------
// the iterator for the IList class
//-----------------------------------------------------------------------
template<class X>
class TIListIterator
{
public:
	TIListIterator()
	{
		m_pList = 0;
		m_pCurrentItem = 0;
	}
	~TIListIterator()
	{
		Break();
	}

	inline X	*GetFirst( CIList *pList )
	{
		Break();
		m_pList = pList;
		m_pCurrentItem = m_pList->GetHead();
		return GetNext();
	}

	inline X	*GetNext()
	{
		m_pCurrentItem = m_pList->GetNext(m_pCurrentItem);
		return (m_pCurrentItem==0)?((X*)0):((X*)m_pCurrentItem->ptr);
	}

	inline void	Break()
	{
		if( m_pCurrentItem )
		{
			m_pCurrentItem->ReleaseRef();
			m_pCurrentItem = 0;
		}
		m_pList = 0;
	}

protected:

	CIList		*m_pList;
	TIListItem	*m_pCurrentItem;
};

//-----------------------------------------------------------------------------
// Double-Linked List Class
//-----------------------------------------------------------------------------
template< class Type > class TLinkedList
{
public:
	//-------------------------------------------------------------------------
	// SElement Structure
	//-------------------------------------------------------------------------
	struct SElement
	{
		Type *data; // Pointer to the data held in the element.
		SElement *next; // Pointer to the next element in the list.
		SElement *prev; // Pointer to the previous element in the list.

		//---------------------------------------------------------------------
		// The element structure constructor.
		//---------------------------------------------------------------------
		SElement( Type *element )
		{
			data = element;
			next = prev = NULL;
		}

		//---------------------------------------------------------------------
		// The element structure destructor.
		//---------------------------------------------------------------------
		~SElement()
		{
			SAFE_DELETE( data );

			if( next )
				next->prev = prev;
			if( prev )
				prev->next = next;
		}
	};

	//-------------------------------------------------------------------------
	// The linked list class constructor.
	//-------------------------------------------------------------------------
	TLinkedList()
	{
		m_pFirst = m_pLast = m_pIterate = m_pTemp = NULL;
		m_totalElements = 0;
	}

	//-------------------------------------------------------------------------
	// The linked list class destructor.
	//-------------------------------------------------------------------------
	~TLinkedList()
	{
		Empty();
	}

	//-------------------------------------------------------------------------
	// Adds the given element to the end of the linked list.
	//-------------------------------------------------------------------------
	Type *Add( Type *element )
	{
		if( element == NULL )
			return NULL;

		if( m_pFirst == NULL )
		{
			m_pFirst = new SElement( element );
			m_pLast = m_pFirst;
		}
		else
		{
			m_pLast->next = new SElement( element );
			m_pLast->next->prev = m_pLast;
			m_pLast = m_pLast->next;
		}

		m_totalElements++;

		return m_pLast->data;
	}

	//-------------------------------------------------------------------------
	// Inserts the given element into the linked list just before nextElement.
	//-------------------------------------------------------------------------
	Type *InsertBefore( Type *element, SElement *nextElement )
	{
		m_pTemp = nextElement->prev;

		m_totalElements++;

		if( m_pTemp == NULL )
		{
			m_pFirst = new SElement( element );
			m_pFirst->next = nextElement;
			nextElement->prev = m_pFirst;

			return m_pFirst->data;
		}
		else
		{
			m_pTemp->next = new SElement( element );
			m_pTemp->next->prev = m_pTemp;
			m_pTemp->next->next = nextElement;
			nextElement->prev = m_pTemp->next;

			return m_pTemp->next->data;
		}
	}

	//-------------------------------------------------------------------------
	// Removes the given element from the linked list and destroys its data.
	//-------------------------------------------------------------------------
	void Remove( Type **element )
	{
		m_pTemp = m_pFirst;
		while( m_pTemp != NULL )
		{
			if( m_pTemp->data == *element )
			{
				if( m_pTemp == m_pFirst )
				{
					m_pFirst = m_pFirst->next;
					if( m_pFirst )
						m_pFirst->prev = NULL;
				}
				if( m_pTemp == m_pLast )
				{
					m_pLast = m_pLast->prev;
					if( m_pLast )
						m_pLast->next = NULL;
				}

				SAFE_DELETE( m_pTemp );

				*element = NULL;

				m_totalElements--;

				return;
			}

			m_pTemp = m_pTemp->next;
		}
	}

	//-------------------------------------------------------------------------
	// Destroys all the elements in the linked list as well as their data.
	//-------------------------------------------------------------------------
	void Empty()
	{
		while( m_pLast != NULL )
		{
			m_pTemp = m_pLast;
			m_pLast = m_pLast->prev;
			SAFE_DELETE( m_pTemp );
		}
		m_pFirst = m_pLast = m_pIterate = m_pTemp = NULL;
		m_totalElements = 0;
	}

	//-------------------------------------------------------------------------
	// Removes all the elements and clears their data pointers.
	// Warning: This function does not destroy the data held be each element.
	//-------------------------------------------------------------------------
	void ClearPointers()
	{
		while( m_pLast != NULL )
		{
			m_pTemp = m_pLast;
			m_pTemp->data = NULL;
			m_pLast = m_pLast->prev;
			SAFE_DELETE( m_pTemp );
		}
		m_pFirst = m_pLast = m_pIterate = m_pTemp = NULL;
		m_totalElements = 0;
	}

	//-------------------------------------------------------------------------
	// Removes the given element and clears its data pointer.
	// Warning: This function does not destroy the data held by the element.
	//-------------------------------------------------------------------------
	void ClearPointer( Type **element )
	{
		m_pTemp = m_pFirst;
		while( m_pTemp != NULL )
		{
			if( m_pTemp->data == *element )
			{
				if( m_pTemp == m_pFirst )
				{
					m_pFirst = m_pFirst->next;
					if( m_pFirst )
						m_pFirst->prev = NULL;
				}
				if( m_pTemp == m_pLast )
				{
					m_pLast = m_pLast->prev;
					if( m_pLast )
						m_pLast->next = NULL;
				}

				m_pTemp->data = NULL;

				SAFE_DELETE( m_pTemp );

				*element = NULL;

				m_totalElements--;

				return;
			}

			m_pTemp = m_pTemp->next;
		}
	}

	//-------------------------------------------------------------------------
	// Iterates through the elements in the linked list.
	//-------------------------------------------------------------------------
	Type *Iterate( bool restart = false )
	{
		if( restart )
			m_pIterate = NULL;
		else
		{
			if( m_pIterate == NULL )
				m_pIterate = m_pFirst;
			else
				m_pIterate = m_pIterate->next;
		}

		if( m_pIterate == NULL )
			return NULL;
		else
			return m_pIterate->data;
	}

	//-------------------------------------------------------------------------
	// Returns the currently iterated element in the linked list.
	//-------------------------------------------------------------------------
	Type *GetCurrent()
	{
		if( m_pIterate )
			return m_pIterate->data;
		else
			return NULL;
	}

	//-------------------------------------------------------------------------
	// Returns the first element in the linked list.
	//-------------------------------------------------------------------------
	Type *GetFirst()
	{
		if( m_pFirst )
			return m_pFirst->data;
		else
			return NULL;
	}

	//-------------------------------------------------------------------------
	// Returns the last element in the linked list.
	//-------------------------------------------------------------------------
	Type *GetLast()
	{
		if( m_pLast )
			return m_pLast->data;
		else
			return NULL;
	}

	//-------------------------------------------------------------------------
	// Returns the next element in the linked list from the given element.
	//-------------------------------------------------------------------------
	Type *GetNext( Type *element )
	{
		m_pTemp = m_pFirst;
		while( m_pTemp != NULL )
		{
			if( m_pTemp->data == element )
			{
				if( m_pTemp->next == NULL )
					return NULL;
				else
					return m_pTemp->next->data;
			}

			m_pTemp = m_pTemp->next;
		}

		return NULL;
	}

	//-------------------------------------------------------------------------
	// Returns a random element from the linked list.
	//-------------------------------------------------------------------------
	Type *GetRandom()
	{
		if( m_totalElements == 0 )
			return NULL;
		else if( m_totalElements == 1 )
			return m_pFirst->data;

		unsigned long element = rand() % m_totalElements;

		m_pTemp = m_pFirst;
		for( unsigned long e = 0; e < element; e++ )
			m_pTemp = m_pTemp->next;

		return m_pTemp->data;
	}

	//-------------------------------------------------------------------------
	// Returns the complete element (including its next and previous pointers).
	//-------------------------------------------------------------------------
	SElement *GetCompleteElement( Type *element )
	{
		m_pTemp = m_pFirst;
		while( m_pTemp != NULL )
		{
			if( m_pTemp->data == element )
					return m_pTemp;

			m_pTemp = m_pTemp->next;
		}

		return NULL;
	}

	//-------------------------------------------------------------------------
	// Returns the total number of elements in the linked list.
	//-------------------------------------------------------------------------
	unsigned long GetTotalElements()
	{
		return m_totalElements;
	}

private:
	SElement *m_pFirst; // First element in the linked list.
	SElement *m_pLast; // Last element in the linked list.
	SElement *m_pIterate; // Used for iterating the linked list.
	SElement *m_pTemp; // Used for temporary storage in various operations.

	unsigned long m_totalElements; // Total number of elements in the linked list.
};

#endif // LIST_H
